import java.util.HashMap;
import java.util.Map;

public class LRU缓存 {


    // 双向链表进行维护
    class DoubleNode {
        int key;
        int val;
        DoubleNode last;
        DoubleNode next;
        public DoubleNode (int key,int val) {
            this.key = key;
            this.val = val;
        }
    }
    // 头尾指针维护
    public DoubleNode head;
    public DoubleNode tail;
    public Map<Integer,DoubleNode> keyNodeMap;
    public int cnt;

    public LRUCache(int capacity) {
        head = tail = null;
        keyNodeMap = new HashMap<>();
        cnt = capacity;
    }

    public int get(int key) {
        // 如果哈希表中存在
        if (keyNodeMap.containsKey(key)) {
            DoubleNode t = keyNodeMap.get(key);
            moveToTail(t);
            return t.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        // 哈希表中存在这个元素
        if (keyNodeMap.containsKey(key)) {
            DoubleNode t = keyNodeMap.get(key);
            t.val = value;
            moveToTail(t);
        } else {
            if (cnt == keyNodeMap.size()) {
                DoubleNode reHead = moveHead();
                if (reHead != null) {
                    keyNodeMap.remove(reHead.key);
                }
            }
            DoubleNode newNode = new DoubleNode(key,value);
            keyNodeMap.put(key,newNode);
            addNode(newNode);
        }
    }

    public void moveToTail (DoubleNode newNode) {
        if (tail == newNode) {
            return;
        }
        if (head == newNode) {
            head = head.next;
            head.last = null;
        } else {
            newNode.last.next = newNode.next;
            newNode.next.last = newNode.last;
        }
        tail.next = newNode;
        newNode.next = null;
        newNode.last = tail;
        tail = newNode;
    }

    public DoubleNode moveHead () {
        if (head == null) {
            return null;
        }
        DoubleNode ans = head;
        if (tail == head) {
            tail = head = null;
        } else {
            head = head.next;
            head.last = null;
        }
        return ans;
    }

    public void addNode (DoubleNode newNode) {
        if (newNode == null) {
            return;
        }
        if (head == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.next = null;
        newNode.last = tail;
        tail = newNode;
    }
}
